LINEAR_ASSIGNMENT

Overview

The LINEAR_ASSIGNMENT function solves the linear sum assignment problem, a fundamental combinatorial optimization problem also known as minimum weight matching in bipartite graphs. Given a cost matrix where each element represents the cost of assigning a particular “worker” to a particular “job,” the function finds the optimal one-to-one assignment that minimizes total cost.

The assignment problem arises in many practical scenarios: assigning taxis to customers to minimize total pickup time, matching employees to tasks based on efficiency, or allocating resources to projects. Formally, for a cost matrix C, the goal is to find an assignment matrix X (where X_{i,j} = 1 if worker i is assigned to job j) that minimizes:

\min \sum_{i} \sum_{j} C_{i,j} X_{i,j}

subject to the constraint that each row is assigned to exactly one column and vice versa (for square matrices), ensuring a complete one-to-one matching.

This implementation uses scipy.optimize.linear_sum_assignment from SciPy, which employs a modified Jonker-Volgenant algorithm. This algorithm is an efficient variant of the classical Hungarian algorithm (also called the Kuhn-Munkres algorithm), with polynomial time complexity of approximately O(n^3) for an n \times n matrix. For further algorithmic details, see the reference by D.F. Crouse (2016) on implementing rectangular assignment algorithms.

The function supports rectangular cost matrices, allowing for unbalanced assignments where the number of workers differs from the number of jobs. In such cases, not every row (or column) will be assigned. The function returns pairs of row and column indices representing the optimal assignments.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=LINEAR_ASSIGNMENT(cost_matrix)

cost_matrix (list[list], required): 2D array of assignment costs, where cost_matrix[i][j] is the cost of assigning row i to column j

Returns (list[list]): 2D list of [[row, col]] pairs representing optimal assignments, or error message string.

Examples

Example 1: Demo case 1

Inputs:

cost_matrix
4	1	3
2	0	5
3	2	2

Excel formula:

=LINEAR_ASSIGNMENT({4,1,3;2,0,5;3,2,2})

Expected output:

Result
0	1
1	0
2	2

Example 2: Demo case 2

Inputs:

cost_matrix
10	19	8	15
10	18	7	17
13	16	9	14

Excel formula:

=LINEAR_ASSIGNMENT({10,19,8,15;10,18,7,17;13,16,9,14})

Expected output:

Result
0	0
1	2
2	3

Example 3: Demo case 3

Inputs:

cost_matrix
9	2	7	8
6	4	3	7
5	8	1	8
7	6	9	4

Excel formula:

=LINEAR_ASSIGNMENT({9,2,7,8;6,4,3,7;5,8,1,8;7,6,9,4})

Expected output:

Result
0	1
1	0
2	2
3	3

Example 4: Demo case 4

Inputs:

cost_matrix
3	1	2
4	6	5

Excel formula:

=LINEAR_ASSIGNMENT({3,1,2;4,6,5})

Expected output:

Result
0	1
1	0

Python Code

import numpy as np
from scipy.optimize import linear_sum_assignment as scipy_linear_sum_assignment

def linear_assignment(cost_matrix):
    """
    Solve the linear assignment problem using scipy.optimize.linear_sum_assignment.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        cost_matrix (list[list]): 2D array of assignment costs, where cost_matrix[i][j] is the cost of assigning row i to column j

    Returns:
        list[list]: 2D list of [[row, col]] pairs representing optimal assignments, or error message string.
    """
    def to2d(x):
        return [[x]] if not isinstance(x, list) else x

    cost_matrix = to2d(cost_matrix)

    # Validate input structure
    if not isinstance(cost_matrix, list) or len(cost_matrix) == 0:
        return "Invalid input: cost_matrix must be a 2D list with at least one row."

    column_count = None

    # Validate structure and convert each value to a finite float
    for row_index, row in enumerate(cost_matrix):
        if not isinstance(row, list) or len(row) == 0:
            return "Invalid input: each row of cost_matrix must be a non-empty list."
        if column_count is None:
            column_count = len(row)
        elif len(row) != column_count:
            return "Invalid input: all rows in cost_matrix must have the same length."

        for col_index, value in enumerate(row):
            try:
                numeric_value = float(value)
            except (TypeError, ValueError):
                return (
                    "Invalid input: cost_matrix values must be numeric. "
                    f"Problem at row {row_index + 1}, column {col_index + 1}."
                )
            if not np.isfinite(numeric_value):
                return (
                    "Invalid input: cost_matrix values must be finite. "
                    f"Problem at row {row_index + 1}, column {col_index + 1}."
                )

    # Convert to NumPy array for scipy compatibility
    try:
        cost_array = np.array(cost_matrix, dtype=float)
    except (ValueError, TypeError) as exc:
        return f"Invalid input: unable to convert cost_matrix to numeric array: {exc}"

    if cost_array.ndim != 2:
        return "Invalid input: cost_matrix must be a 2D list."

    # Solve the assignment problem using scipy's Hungarian algorithm
    try:
        row_indices, col_indices = scipy_linear_sum_assignment(cost_array)
    except Exception as exc:
        return f"Solver error: {exc}"

    # Build the result as a 2D list of integer index pairs
    assignment = [
        [int(row_indices[i]), int(col_indices[i])] 
        for i in range(len(row_indices))
    ]
    return assignment

Overview

Excel Usage

Examples

Python Code

Online Calculator